package problem42_Trapping_Rain_Water;

public class MySolution {
	  public int trap(int[] height) {
		  int start=0,end=0,area=0;
		  while(start+2<height.length){
			while(start+1<height.length&&height[start+1]>=height[start]){
				start++;
			}
			end=start+1;
			while(end+1<height.length&&!(height[end]>height[end-1]&&height[end]>=height[end+1])){
				end++;
			}
			int endTmp=end;
			while(end+1<height.length&&height[start]>height[end]){
				end++;
				while(end+1<height.length&&!(height[end]>height[end-1]&&height[end]>=height[end+1])){
					end++;
				}
				endTmp=height[endTmp]>height[end]?endTmp:end;
			}
			area+=calculateArea(start,endTmp,height);
			start=endTmp;
		  }
		  return area;
	  }
	  
	  private int calculateArea(int start,int end,int[] height){
		  if(start+1==end||start==end) return 0;
		  int minHeight=Math.min(height[start], height[end]);
		  int area=(end-start-1)*minHeight;
		  for(int i=start+1;i<end;i++){
			  area-=Math.min(minHeight, height[i]);
		  }
		  return area;
	  }
	  
	  public static void main(String[] args){
		  System.out.println(new MySolution().trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
	  }
}
